import random


class QuickSort:
    def __init__(self, array):
        self.array = array

    def get_length(self):
        return len(self.array)

    def quick_sort(self, lo, hi):
        if hi-lo < 2:
            return
        m = self.partition(lo, hi)
        self.quick_sort(lo, m)
        self.quick_sort(m, hi)

    def partition(self, lo, hi):
        self.swap(lo, lo+random.randint(1,100) % (hi-lo+1))
        pivot = self.array[lo]  # 候选轴点
        while lo < hi:
            while lo < hi and pivot <= self.array[hi]: # 从右往左扫遇到比轴点小的就往左堆丢
                hi -= 1
            self.array[lo] = self.array[hi]
            while lo < hi and self.array[lo] <= pivot: # 从左往右扫遇到比轴点大的就往右堆丢
                lo += 1
            self.array[hi] = self.array[lo]
        self.array[lo] = pivot
        return lo

    def swap(self, lo, hi):
        self.array[lo], self.array[hi] = self.array[hi], self.array[lo]


quick = QuickSort([2, 3, 4, 1, 7, 5, 7])
quick.quick_sort(0, quick.get_length()-1)
print(quick.array)
